package Tree;

/**
 * @author yyq
 * @create 2022-01-13 15:09
 *
 * 平衡二叉树
 */
public class AVL {
    public static Integer MaxDeep=0;
    public static AVLNode NODE=null;
    public static void main(String[] args) {
        AVLNode root = new AVLNode(66);
        root.left=new AVLNode(60);
        root.right=new AVLNode(77);
        root.right.right=new AVLNode(88);
        root.right.right.right=new AVLNode(99);
        root.right.left=new AVLNode(75);
        NodeDeep(root,1);
        System.out.println("此树高度为"+MaxDeep);
        MaxDeep=0;
        inOrder(root);
        MiniNotBalacneTree(root);
        System.out.println("最小不平衡二叉树的节点为"+NODE.data);
    }

    public static void MiniNotBalacneTree(AVLNode root){
        int leftDeep=0;
        int rightDeep=0;
        if(root.left!=null){
            NodeDeep(root.left,1);
            leftDeep = MaxDeep;
            MaxDeep=0;
        }

        if(root.right!=null){
            NodeDeep(root.right,1);
            rightDeep = MaxDeep;
            MaxDeep=0;
        }


        if(Math.abs(rightDeep-leftDeep)>=2){
            NODE=root;
        }

        if(root.left!=null){
            MiniNotBalacneTree(root.left);
        }

        if(root.right!=null){
            MiniNotBalacneTree(root.right);
        }


    }


    public static void inOrder(AVLNode root){
        if(root.left!=null){
            inOrder(root.left);
        }
        System.out.print(root.data+" ");
        if (root.right!=null){
            inOrder(root.right);
        }
    }
    // 获取一个节点的左子树 或者 右子树 的最大高度
    public static void NodeDeep(AVLNode root,Integer deep){
        if(deep>MaxDeep) MaxDeep=deep;
        if(root.left!=null){
            NodeDeep(root.left,deep+1);
        }
        if(root.right!=null){
            NodeDeep(root.right,deep+1);
        }
    }

}


class AVLNode{
    public AVLNode(Integer data) {
        this.data = data;
    }

    Integer data;
    AVLNode left;
    AVLNode right;
}
